#define _CRT_SECURE_NO_WARNINGS

#pragma once

#include "Heap.h"


void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}
void jsup(int* h, int c)
{
	int p = (c - 1) / 2;
	while (c > 0)
	{
		if (h[p] > h[c])
		{
			Swap(&h[p], &h[c]);
			c = p;
			p = (c - 1) / 2;
		}
		else
			break;
	}
}
void jsdown(int* h, int size, int p)
{
	int c = p * 2 + 1;
	while (c < size)
	{
		if (c + 1 < size && h[c] > h[c + 1])
			c++;
		if (h[p] > h[c])
		{
			Swap(&h[p], &h[c]);
			p = c;
			c = p * 2 + 1;
		}
		else
			break;
	}
}
void HeapInit(Heap* h)
{
	h->_p = NULL;
	h->_size = h->_capacity = 0;
}
void HeapPush(Heap* h, int x)
{
	if (h->_size == h->_capacity)
	{
		int new = h->_capacity == 0 ? 4 : h->_capacity * 2;
		int* p = (int*)realloc(h->_p, new * sizeof(int));
		h->_p = p;
		h->_capacity = new;
	}
	h->_p[h->_size] = x;

	h->_size++;
	jsup(h->_p, h->_size - 1);
}


void HeapPop(Heap* h)
{
	Swap(&h->_p[0], &h->_p[h->_size - 1]);
	h->_size--;
	jsdown(h->_p, h->_size, 0);
}
int HeapTop(Heap* h)
{
	return h->_p[0];
}
void HeapPrint(Heap* h)
{
	for (int i = 0; i < h->_size; i++)
	{
		printf("%d ", h->_p[i]);
	}
	printf("\n");
}
int HeapSize(Heap* h)
{
	return h->_size;
}
int HeapCapacity(Heap* h)
{
	return h->_capacity;
}
bool HeapEmpty(Heap* h)
{
	return h->_size == 0;
}